#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/22 9:38
# ===========================================
#       题目名称： 23. 合并 K 个升序链表
#       题目地址： https://leetcode.cn/problems/merge-k-sorted-lists/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
import math
from utils import StringUtils


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """
        实现思路：
            当前长度 和 下一个长度 比谁长 谁长谁就是基准
    """

    def mergeKLists(self, lists):
        if not lists:
            return None
        res = None
        while lists:
            element = lists.pop()
            if res:
                temp_res = res
                while temp_res and temp_res.next:
                    temp_res = temp_res.next
                temp_res.next = element
            else:
                res = element

        def sort_list(head):
            # 将链表转换为列表
            values = []
            current = head
            while current:
                values.append(current.val)
                current = current.next
            # 对列表进行排序
            sorted_values = sorted(values)
            # 将排序后的值重新赋给链表
            current = head
            for value in sorted_values:
                current.val = value
                current = current.next
            return head
        return sort_list(res)

    def mergeKLists4(self, lists):
        # 定义一个函数用于合并两个已排序的链表成一个升序链表
        def merge(l1, l2):
            # 如果其中一个链表为空，则返回另一个
            if not l1 or not l2:
                return l1 or l2
            # 比较两个链表头节点的值，并且将较小的值作为新链表的头结点
            if l1.val < l2.val:
                l1.next = merge(l1.next, l2)  # 递归地合并剩余部分
                return l1
            else:
                l2.next = merge(l2.next, l1)
                return l2

        # 定义归并排序函数，将链表列表划分为两组，递归地合并每组的链表
        def merge_sort(lists):
            if not lists:
                return None
            if len(lists) == 1:
                return lists[0]
            mid = len(lists) // 2
            left = merge_sort(lists[:mid])
            right = merge_sort(lists[mid:])
            return merge(left, right)

        return merge_sort(lists)

    def mergeKLists3(self, lists):
        if not lists:
            return None
        res = None
        while lists:
            element = lists.pop()
            if not element:
                continue
            if not res:
                res = element
            else:
                # 最大的 往后贴
                l1 = res
                l2 = element
                res = None
                while l1 or l2:
                    while l2 and (not l1 or l2.val < l1.val):
                        if res:
                            temp_res = res
                            while temp_res.next:
                                temp_res = temp_res.next
                            temp_res.next = ListNode(l2.val)

                        else:
                            res = ListNode(l2.val)
                        l2 = l2.next
                    while l1 and (not l2 or l1.val <= l2.val):
                        if res:
                            temp_res = res
                            while temp_res.next:
                                temp_res = temp_res.next
                            temp_res.next = ListNode(l1.val)
                        else:
                            res = ListNode(l1.val)
                        l1 = l1.next
        return res

    def mergeKLists2(self, lists):
        """
            时间超出限制
        """
        if not lists:
            return None
        MAX_VALUE = (math.pow(2, 31) - 1) // 1
        res = None
        while lists:
            element = lists.pop()
            if not element:
                continue
            if not res:
                res = element
            else:  # l1 l2 进行合并
                l1 = res
                l2 = element
                res = ListNode(MAX_VALUE)
                while l1 or l2:
                    while l2 and (not l1 or l2.val < l1.val):
                        if res.val is MAX_VALUE:
                            res.val = l2.val
                        else:
                            temp_res = res
                            while temp_res.next:
                                temp_res = temp_res.next
                            temp_res.next = ListNode(l2.val)
                        l2 = l2.next
                    while l1 and (not l2 or l1.val <= l2.val):
                        if res.val is MAX_VALUE:
                            res.val = l1.val
                        else:
                            temp_res = res
                            while temp_res.next:
                                temp_res = temp_res.next
                            temp_res.next = ListNode(l1.val)
                        l1 = l1.next
        return res


if __name__ == '__main__':
    s = Solution()
    # [1,1,2,3,4,4,5,6]
    print(StringUtils.to_string(s.mergeKLists(lists=[
        ListNode(1, ListNode(4, ListNode(5))),
        ListNode(1, ListNode(3, ListNode(4))),
        ListNode(2, ListNode(6)),
    ])))
    # []
    print(StringUtils.to_string(s.mergeKLists(lists=None)))
    # []
    print(StringUtils.to_string(s.mergeKLists(lists=[None, ])))
